package conclusion;

import java.util.Arrays;
import java.util.HashMap;

/**
 * DP:
 * A DP is an algorithm technique which is usually based on a recurrent
 * formula and one or some starting states. A sub-solution of the problem
 * is constructed from previously found ones. DP have a polynomial complexity
 * which assures a much faster running time than other techniques like 
 * backtracking, brute-force.
 * 
 * 
 * 
 * LeetCode ex:
 * 	edit distance O(M+N)
 *  scramble string
 *  
 * 
 * 
 * @author hangou
 *
 */
public class DynamicProgramming {
	
	/**
	 * Same problem see LeetCode_day13, which uses a greedy approach
	 * 
	 */
	public static void textJustification(){
		
	}
	
	/**
	 * Notice: all weights and values are non-negative.
	 * 
	 * Subproblem: 
	 * m[i,w] - maximum value that can be attained with remaining weight <= w using items up to i.
	 * 把前i个物品装进容量为j的背包可以获得的最大价值
	 * Define subproblem recursively:
	 * m[i,w] = max{m[i-1,w], m[i-1,w-wi]+vi if w > wi} (not take item i or take)
	 * 
	 * Another way to solve it is to use graph search technique, search tree
	 * 
	 * @param weight
	 * @param value
	 * @param capacity
	 */
	public static void knapsack0_1_Original(int[] weight, int[] value, int capacity){
		int[][] m = new int[weight.length+1][capacity+1];
		boolean[][] parent = new boolean[weight.length+1][capacity+1];
		
		for(int i = 0 ; i < m[0].length ; i++)
			m[0][i] = 0;//d[i]=0
		for(int i = 1 ; i < weight.length+1 ; i++)
			for(int j = 0 ; j < capacity+1 ; j++){
				if(j >= weight[i-1]){
					if(m[i-1][j] < m[i-1][j-weight[i-1]] + value[i-1]){//d[j]<d[j-weight[i-1]]+value[i-1]
						m[i][j] = m[i-1][j-weight[i-1]] + value[i-1]; parent[i][j] = true;
						continue;
					}
				}
				m[i][j] = m[i-1][j];//d[j] stays
				parent[i][j] = false;
			}
				
		System.out.println("The maximum value we can get is: "+m[weight.length][capacity]);
		System.out.println("The item we take is: ");
		int i = weight.length, j = capacity;
		while(i > 0 && j > 0){
			if(parent[i][j]){
				j-=weight[i-1];
				System.out.print(i+" ");
			}
			i--;
		}
	}

	/**
	 * 使用滚动数组的方法来减少needed空间Space
	 * Because for m[i][j], we only need m[i-1,w] & m[i-1,w-wi] at most,
	 * before updating d[j], we have m[i-1][j] stored in d[j]
	 * after that, we have m[i][j];
	 * 
	 * @param weight
	 * @param value
	 * @param capacity
	 */
	public static void knapsack0_1_Opt(int[] weight, int[] value, int capacity){
		boolean[][] parent = new boolean[weight.length+1][capacity+1];
	
		int[] d = new int[capacity+1]; 
		Arrays.fill(d, 0);
		
		for(int i = 1 ; i < weight.length + 1 ; i++)
			for(int j = capacity ; j >= 0 ; j--)
				//notice, we cannot write for(int j = 0 ; j < capacity+1 ; j++)
				//because this would cause re-take the same item many times
				//for example, if weight[i-1] = 2, value[i-1] = 4, d[2] and d[4] would take item i-1
				//however, if we calculate d[2] before d[4], then we have d[2] = 4,
				//when loop comes to d[3], it will be like d[4] = d[2] + 4 = 8.
				if(j >= weight[i-1] && d[j-weight[i-1]] + value[i-1] > d[j]) {
					d[j] = d[j-weight[i-1]] + value[i-1];
					parent[i][j] = true;
				}else{
					parent[i][j] = false;
				}
		
		System.out.println("The maximum value we can get is: "+ d[capacity]);
		System.out.println("The item we take is: ");
		int i = weight.length, j = capacity;
		while(i > 0 && j > 0){
			if(parent[i][j]){
				j-=weight[i-1];
				System.out.print(i+" ");
			}
			i--;
		}
	}
	
	/**
	 * Using recursion, the search space would be exponential.
	 * @param weight
	 * @param value
	 * @param capacity
	 */
	public static void knapsack0_1_SearchTree(int[] weight, int[] value, int capacity){
		boolean[][] path = new boolean[2][weight.length];
		int[] totalV = new int[2];
		HashMap<Integer, boolean[]> map = new HashMap<Integer, boolean[]>();
		knapsackSearch(0, weight, value, capacity, path, totalV, map);
		System.out.println();
		System.out.println("The maximum value we can get is: "+ map.keySet().iterator().next());
		System.out.println("The item we take is: ");
		boolean[] ress = map.entrySet().iterator().next().getValue();
		for(int i = 0 ; i < ress.length ; i++)
			if(ress[i]) System.out.print(i + " ");
	}
	
	private static void knapsackSearch(int i, int[] weight, int[] value, int capacity, boolean[][] path, int[] totalV, HashMap<Integer, boolean[]>res){
		if(i == weight.length) {
			path[1] = totalV[0] > totalV[1] ? path[0]: path[1];
			totalV[1] = totalV[0] > totalV[1] ? totalV[0] : totalV[1];
			
			res.put(totalV[1], path[1]);
			return;
		}else{
			if(weight[i] <= capacity){
				boolean[][] npath = new boolean[2][path[0].length];
				npath[0] = Arrays.copyOf(path[0], path[0].length);
				npath[0][i] = true;
				int[] ntotalV = new int[2];
				ntotalV[0] = totalV[0] + value[i];
				if(ntotalV[0] > totalV[1]){
					ntotalV[1] = ntotalV[0];
					//Arrays.co
				}
				ntotalV[1] = ntotalV[0] > totalV[1] ? ntotalV[0] : totalV[1];
				npath[1] = ntotalV[0] > totalV[1] ? npath[0]: path[1];
				knapsackSearch(i+1, weight, value, capacity-weight[i], npath, ntotalV,res);
			}else{
				knapsackSearch(i+1, weight, value, capacity, path, totalV,res);
			}
		}
	}

	/**
	 * Classical dynamic programming example.
	 * 
	 * DP(i,j) = min(
	 * 				cost of replace(i,j) + DP(i+1, j+1),
	 * 				cost of delete i     + DP(i+1, j),
	 *              cost of insert j     + DP(i, j+1)
	 *              )
	 * @param s1
	 * @param s2
	 */
	public static void editDistance(String s1, String s2){
		char[] c1 = s1.toCharArray();
		char[] c2 = s2.toCharArray();
		
		int x = s1.length(), y = s2.length();
		int[] dppre = new int[y+1];
		int[] dp = new int[y+1];
		int[][] parent = new int[x][y];
		for(int i = x-1 ; i >= 0 ; i--){
			for(int j = y ; j >= 0 ; j--){
				if(j == y) continue;
				if(c1[i] == c2[j]){
					parent[i][j] = 1;
					dp[j] = dppre[j+1];
				}else{
					int cost1 = dppre[j+1] + 1; //replace
					int cost2 = dp[j+1] + 1; //insert
					int cost3 = dppre[j] + 1;//delete
					dp[j] = cost1 > cost2 ? cost2 : cost1;
					dp[j] = dp[j] > cost3 ? cost3 : dp[j];
					if(dp[j] == cost1) parent[i][j] = 2;
					else if(dp[j] == cost2) parent[i][j] = 3;
					else parent[i][j] = 4;
				}
			}
			dppre = Arrays.copyOf(dp, dp.length);
		}
		System.out.println("The minimum cost is: "+ dp[0]);
	}
	
	
	/**
	 * Classical dynamic programming
	 * @param a
	 * @param b
	 */
	public static void longestCommonSubsequence(String a, String b){
		
	}
	
	
	public static void longestPalindromicSubstring(String s){
		char[] c = s.toCharArray();
		int begin = 0 , end = 0;
		boolean[][] t = new boolean[c.length][c.length];
		for(int i = 0 ; i < c.length ; i++) {
			t[i][i] = true;
			if(i > 0 && c[i-1] == c[i]) t[i-1][i] = true;
		}
		for(int len = 3 ; len <= c.length ; len++) {
			for(int start = 0 ; start <= c.length-len ; start++){
				if(c[start] == c[start+len-1] && t[start+1][start+len-2]) {
					t[start][start+len-1] = true;
					begin = start; end = start+len-1;
				}
			}
		}
		System.out.println(s.substring(begin, end+1));
	}
	
	
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		knapsack0_1_Original(new int[]{3,4,5}, new int[]{4,5,6}, 10);
		System.out.println();
		knapsack0_1_Opt(new int[]{3,4,5}, new int[]{4,5,6}, 10);
		System.out.println();
		knapsack0_1_SearchTree(new int[]{3,4,5}, new int[]{4,5,6}, 10);
		System.out.println();
		editDistance("hello","hella");
		System.out.println();
		longestPalindromicSubstring("baabweooews");
	}

}
